package com.example.lcpractice.lc;

import com.example.lcpractice.datastructure.ListNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * [22]括号生成.java
 * //数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * //
 * // 示例 1：
 * //
 * //输入：n = 3
 * //输出：["((()))","(()())","(())()","()(())","()()()"]
 * //
 * // 示例 2：
 * //
 * //
 * //输入：n = 1
 * //输出：["()"]
 * //
 * // 提示：
 * //
 * // 1 <= n <= 8
 * //
 * // Related Topics 字符串 动态规划 回溯 👍 2820 👎 0
 */
public class Lc22 {
    public static void main(String[] args) {
        List<String> strings = generateParenthesis2(2);
        System.out.println(strings);
    }


    static List<String> list = new LinkedList();

    /**
     * dfs递归回溯法，见lc22.jpg
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis(int n) {
        backtracking("", 0, 0, n);
        return list;
    }

    /**
     * 动态规划法
     *
     * @param n
     * @return
     */
    public static List<String> generateParenthesis2(int n) {
        if (n == 0) {
            return new ArrayList<>();
        }
        // 这里 dp 数组我们把它变成列表的样子，方便调用而已
        List<List<String>> dp = new ArrayList<>(n);

        List<String> dp0 = new ArrayList<>();
        dp0.add("");
        dp.add(dp0);

        for (int i = 1; i <= n; i++) {
            List<String> cur = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                List<String> str1 = dp.get(j);
                List<String> str2 = dp.get(i - 1 - j);
                for (String s1 : str1) {
                    for (String s2 : str2) {
                        // 枚举右括号的位置
                        cur.add("(" + s1 + ")" + s2);
                    }
                }
            }
            dp.add(cur);
        }
        return dp.get(n);
    }

    /**
     * 递归回溯主方法
     *
     * @param cur   暂存区字符串
     * @param open  开（左）括号数目
     * @param close 闭（右）括号数目
     * @param max   即输入的指定的n
     */
    public static void backtracking(String cur, int open, int close, int max) {
        //当字符串cur长度为2*n，则加入列表
        if (cur.length() == max * 2) {
            list.add(cur);
            return;
        }
        //只要"("数目小于n，就可以添加"(",
        // 为什么是"<"，假设n=2,此处open为"1",会进入方法块，递归则变2
        if (open < max) {
            backtracking(cur + "(", open + 1, close, max);
        }
        //闭括号数不能超过开括号,就可以添加")"
        if (close < open) {
            backtracking(cur + ")", open, close + 1, max);
        }
    }


}
